package algorithm.dichotomy.realize;

/**
 * @author: 柒月
 * @date: 2025/5/1 上午10:29
 * @version: 1.0
 */
public class Dichotomy {

    /**
     * 简单的二分查找算法
     *
     * @param nums   要查找的数组必须要有序
     * @param target 查找的目标值
     * @return 在数组中是否找到目标值
     */
    public static boolean exist(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return false;
        }
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                return true;
            }
        }
        return false;
    }

    /**
     * @param nums   要查找的数组必须要有序
     * @param target 目标值
     * @return 返回最左侧等于目标值的下标
     */
    public static int findLeft(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1, mid, ans = -1;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (nums[mid] >= target){
                ans = mid;
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }
        if (ans == -1) return -1;
        return nums[ans] == target ? ans : -1;
    }

    /**
     * @param nums   要查找的数组必须要有序
     * @param target 目标值
     * @return 返回最右侧等于目标值的下标
     */
    public static int findRight(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return -1;
        }
        int left = 0, right = nums.length - 1, mid, ans = -1;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            if (nums[mid] <= target){
                ans = mid;
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        if (ans == -1) return -1;
        return nums[ans] == target ? ans : -1;
    }
}
